Placement is a step in physical design flow of an integrated circuit (IC) where the locations of cells or circuit modules of the user design are assigned within the chip's core area. The electronic design automation (EDA) tool that is used for placement is referred to as a placer. The placer receives a netlist that describes the circuit design and produces a placement layout. In programmable ICs such as field-programmable gate arrays (FPGAs), placement maps the cells of the user design into FPGA's existing logic blocks sites.
Placement in ICs is usually performed in two stages, global and detailed placement. Global placement distributes the cells over the placement region with the goal to reduce the global congestion, global timing, and wirelength. Detailed placer uses a better timing model than global placement with the goal of resolving local congestion and local timing problems.
Placers might use one or more objectives such as minimizing wire lengths, meeting user design timing objectives, reducing wiring congestions, and minimizing power consumption. A mathematical function (usually referred to as cost function or objective function) that expresses these objectives is defined. The cost function is used to find an optimized solution for the placement. A classic example of a combinatorial optimization problem is the travelling salesman problem. Given a group of cities and a function for calculating the cost of travelling between any two cities, the goal is to plan the salesman's optimal route which passes through each city once and returns to the starting point, minimizing the total cost.
Travelling salesman problem belongs to the class of nondeterministic polynomial time complete (NP-complete) problems where there are no known efficient algorithms that find the exact solution for the problem. The computing cost for finding an exact optimal solution increases exponentially with the number of variables (in this example, number of cites) in the cost functions. An iterative improvement strategy for optimizing the cost function is to start with a known configuration, rearrange the configuration (e.g., change the path of the salesman through different cities) until the cost is improved. The rearranged configuration is then used as a new configuration and the process continues until no further improvements can be achieved.
Different optimization methods such as simulated annealing have been used in the past for placing IC components. Simulated annealing is inspired by annealing in metallurgy where a solid state metal is heated to a high temperature to ensure a random state for the atoms followed by a gradual cooling to allow the atoms to place themselves in a pattern that corresponds to a global minimum for a perfect crystal. Simulated annealing (i) starts with a given initial placement and a global parameter (referred to as temperature) that is gradually decreased, (ii) calculates a score for the placement, (iii) moves a cell to a new location, (iv) calculates the change in the score due to the move made, (v) depending on the change and the value of the global parameter, accepts or rejects the move and decreases the global parameter. The technique repeats steps (ii) to (v) until the global parameter becomes zero.
In accepting a move, simulating annealing techniques initially allow “uphill” moves that worsen the score but gradually decrease the chance of allowing such moves and select better or “downhill” moves. The initial allowance for “uphill” moves avoids being stuck at local minimum points. FIG. 1 illustrates a graph 100 that shows the results of a prior art simulated annealing after many iterations. As shown, the process starts with an initial cost function value 105. The cost function value is gradually decreased during iterations until a final cost function value 110 is reached. However, several times during the iterations, the value of the cost function worsens to local maximums 115-120 to allow hill climbing in order to avoid local minimums 125-130.
Without accepting the worsen solutions, the process would be stuck at local minimums 125-130. Simulated annealing requires many iterations, gradually reduces the probability of accepting worse solutions, and continues to optimize the cost function until the global parameter reaches zero.